# 组合总数


class Solution:

    def combinationSum(self, candidates, target):


        def dfs(candidates, begin, size, path, res, target):
            if target < 0:
                return
            if target == 0:
                res.append(path)

            for index in range(begin, size):
                dfs(candidates, index, size, path+[candidates[index]], res, target - candidates[index])


        size = len(candidates)
        if size == 0 :
            return []
        path = []
        res = []
        dfs(candidates, 0, size, path, res, target)

        return res




if __name__ == "__main__":

    c = [2,3,6,7]
    t = 7

    sol = Solution()
    res = sol.combinationSum(c, t)
    print(res)




